package com.company;
class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
}
public class Solution86 {
    public ListNode partition(ListNode head, int x) {
        ListNode smaller= new ListNode(0);
        ListNode larger= new ListNode(0);
        ListNode sTail=smaller;
        ListNode lTail=larger;
        ListNode tmp=head;
        while(tmp!=null){
            if(tmp.val<x){
                sTail.next=tmp;
                sTail=tmp;
            }
            else{
                lTail.next=tmp;
                lTail=tmp;
            }
            tmp=tmp.next;
        }
        lTail.next=null;
        sTail.next=larger.next;
        return smaller.next;
    }
}
